Modèle de Barabási-Albert
construit itérativement de la manière suivante :
- On part d'un graphe initial \(G_0=(\mathcal V_0,\mathcal E_0)\)
- À chaque étape \(t\),
- On ajoute un sommet \(t\) à \(\mathcal V_{t-1}\), de manière à avoir \(\mathcal V_t=\{1,\dots,t\}\) et \(n_t:=\lvert\mathcal V_t\rvert=n_0+t\)
- On connecte \(t\) à \(V_t\in\mathcal V_{t-1}\) (aléatoirement), de manière à avoir \(\mathcal E_t=\mathcal E_{t-1}\cup\{(V_t,t)\}\) et \(e_t:=\lvert\mathcal E_t\rvert=\lvert\mathcal E_0\rvert+t\)
- \(V_t\) est choisie de la façon suivante : $$\forall v\in\mathcal V_{t-1},\quad{\Bbb P}(V_t=v|V_1^{t-1})=\alpha\frac1{n_{t-1} }+(1-\alpha)\frac{D_{t-1}(v)}{2e_{t-1} }$$avec \(D_{t-1}(v)\) le degré de \(v\) dans \(G_t\)
- c'est approximativement un Graphe en loi de puissance, avec \(\beta=\frac{3-\alpha}{1-\alpha}\)
